package ds.tree;
/**
 * Class that generates tree from the traversal data.
 * 
 * @author monkey
 *
 */
public class BTFromTraversal {
	
	public BTFromTraversal() {
		postIndex=postorder.length-1;
	}
	private static class TreeNode{
		int value;
		TreeNode left = null;
		TreeNode right = null;
		
		TreeNode(int val){
			this.value = val;
		}
		
		public String toString(){
			return String.valueOf(value);
		}
	}
//	private int[] inorder = new int[] {4,2,5,1,3};
//	private int[] preorder = new int[]{1,2,4,5,3};
//	private int[] postorder= new int[]{4,5,2,3,1};

	private int[] inorder = new int[] {2,1};
	private int[] preorder = new int[]{1,2};
	private int[] postorder= new int[]{2,1};
	
	private static int preIndex = 0;
	private static int postIndex = 0;
	
	private TreeNode buildTreeFromPreOrder(int start, int end){
		if(start > end){
			return null;
		}
		int val = preorder[preIndex++];
		TreeNode node = new TreeNode(val);
		int inIndex = searchInOrder(val);
		node.left = buildTreeFromPreOrder(start, inIndex-1);
		node.right = buildTreeFromPreOrder(inIndex+1,end);
		
		return node;
	}
	private TreeNode buildTreeFromPostOrder(int start, int end){
		if(start > end){
			return null;
		}		
		int val = postorder[postIndex--];
		TreeNode node = new TreeNode(val);
		int inIndex = searchInOrder(val);
		node.right = buildTreeFromPostOrder(inIndex+1, end);
		node.left = buildTreeFromPostOrder(start,inIndex-1);		
		return node;
	}
	private int searchInOrder(int val){
		int i = 0;
		while(inorder[i++] != val){}
		return --i;
	}
	public void inOrderTraversal(TreeNode node){
		if(node == null){
			return;
		}
		inOrderTraversal(node.left);
		System.out.print(node + " ");
		inOrderTraversal(node.right);
	}
	public static void main(String[] args) {
		BTFromTraversal bt = new BTFromTraversal();
		BTFromTraversal.TreeNode node = bt.buildTreeFromPreOrder(0, bt.inorder.length-1);
		bt.inOrderTraversal(node);
		System.out.println();
		node = bt.buildTreeFromPostOrder(0, bt.inorder.length-1);
		bt.inOrderTraversal(node);
	}
	
}
